package org.example.string;

public class keywords {
    public static void main(String[] args) {
        //找出字符串中第一个匹配项的下标

        //给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
        String haystack = "hello";
        String needle = "lo";
        System.out.println(find2(haystack,needle));
    }
    //将之前的写的KMP算法精简后的最终代码
    public static int find2(String haystack,String needle){
        //判断两者长度是否为空，模式串是否长于主串，二者达成其一就不需要匹配了
        if (haystack.length()==0 || needle.length()==0 || haystack.length()<needle.length()){
            return -1;
        }
        //获取next数组
        int[] next = getNext2(needle);
        int i = 0;
        int j = 0;
        while(haystack.length()-i>=needle.length()-j){
            if (haystack.charAt(i)!=needle.charAt(j)){
                //当该字符无法于主串进行匹配成功，通过next函数查看是否可以移位，即将j指针回溯，i指针不动
                j=next[j];
                //当j<0时，说明模式串第一个字符也没有成功匹配且没有移位，所以需要模式串第一位重新与主串下一位进行匹配
                if (j<0){
                    j=0;
                    i++;
                }
            }else{
                i++;
                j++;
            }
            //此时j指针已匹配完成
            if (j>=needle.length()){
                return i-j;
            }
        }
        return -1;
    }
    //将getNext函数改进
    public static int[] getNext2(String s){
        int len = s.length();
        //next的值表示在该下标之前的前后缀的最大长度，例如next[3]=5，表示在字符串位于3下标的字符的前后缀的长度为5
        int[] next = new int[len];
        next[0] = -1;
        int i=0;
        int j=-1;
        while(i<len-1){
            //每次比较该字符对应的next值，如果成功则该字符的next值是回溯的next值+1，否则一直到next[0]=-1，即第一位为止，此时表明该字符之前没有前后缀，即next=0
            if (j==-1 || s.charAt(i)==s.charAt(j)){
                next[++i] = ++j;
            }else {
                //回溯字符的next值，如果不等，则根据next继续向前回溯直到到达首位字符
                j=next[j];
            }
        }
        return next;
    }
    //暴力破解
    public static int find3(String haystack,String needle){
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }

    //KMP算法
    public static int find(String haystack,String needle){
        if (haystack.length()==0 || needle.length()==0 || haystack.length()<needle.length()){
            return -1;
        }
        int[] next = getNext(needle);
        int i = 1;
        int j = 1;
        char[] hay = new char[haystack.length()+1];
        for (int k = 0; k <haystack.length(); k++) {
            hay[k+1] = haystack.charAt(k);
        }
        char[] nee = new char[needle.length()+1];
        for (int k = 0; k <needle.length(); k++) {
            nee[k+1] = needle.charAt(k);
        }
        while(hay.length-i>=nee.length-j){
            if (hay[i]!=nee[j]){
                j=next[j];
                if (j<=0){
                    j=1;
                    i++;
                }
            }else{
                i++;
                j++;
            }
            if (j>needle.length()){
                return i-j;
            }
        }
        return -1;
    }
    //KMP算法中next数组的求解
    public static int[] getNext(String s){
        //char[] chars = s.toCharArray();
        char[] chars = new char[s.length()+1];
        for (int i = 1; i <= s.length(); i++) {
            chars[i] = s.charAt(i-1);
        }
        int[] next = new int[chars.length];
        next[0] = -1;
        next[1] = 0;
        int i=1;
        int j=0;
        while(i<chars.length-1){
            if (j==0 || chars[i]==chars[j]){
                next[++i] = ++j;
            }else {
                j=next[j];
            }
        }
        return next;
    }
}
